1. Field of the Invention
The present invention relates generally to a channel encoding apparatus and method, and in particular, to a channel encoding apparatus and method in which parity bits are partially set to artificial erroneous bits, and full parity bits are created by correcting the erroneous bits using a channel decoding apparatus provided at a receiver of a communication system.
2. Description of the Related Art
Typically, a channel encoder forms codewords by adding parity bits to message bits to be transmitted, and a channel decoder extracts the message bits from the received codewords by carrying out the reverse of the channel encoding.
FIG. 1 illustrates data structures in typical channel encoding and decoding.
Referring to FIG. 1, the channel encoder creates an n-bit codeword by adding an m-bit parity bit stream to a k-bit message, prior to transmission.
Information loss or errors takes place during data transmission or data storage due to noise, distortion and interference in various forms in a communication system or a data storing system. Error correction is a requisite against such errors.
The channel decoder, therefore, receives errors on a channel as well as the n-bit codeword and recovers the k-bit message by correcting for the errors.
As illustrated in FIG. 2, the typical channel encoder is comprised of an input buffer 21 for receiving message bits to be transmitted, a parity calculator 22 for calculating parity bits based on the message bits, a pre-processor 24 for calculating a generator matrix having codeword generation information by a matrix operation, specifically using the relationship of GHT=0 (G is the generator matrix and H is a parity check matrix), a memory 23 for storing the matrix information, and an output buffer 25 for outputting codewords. More specifically, the parity calculator 22 calculates the parity bits using the message bits received from the input buffer 21 referring to the matrix information stored in the memory 23. The output buffer 25 outputs the message bits received from the input buffer 21 and the parity bits received from the parity calculator 22.
In the above-described general channel encoding, it is known that the computation complexity of the pre-processor 24 is 0(n3) where n is a codeword length, and the actual computation complexity of the parity calculator 22 is 0(n2).
As a channel code, an LDPC (Low-Density Parity-Check) code exhibits performance close to the Shannon Limit representing the theoretical limit of channel coding performance. Yet, its codeword length is so large that an LDPC encoder is a highly complex device, and the LDPC code requires a large memory capacity. Especially it is known that hardware complexity is larger in the LDPC encoder than in the LDPC decoder.
To overcome the complexity, a conventional LDPC encoding method, as described in “Efficient Encoding of Low-Density Parity-Check Codes”, Thomas J. Richardson and Rudiger L. Urbanke, IEEE Transaction on Information Theory February 2001, decomposes a parity-check matrix into partition matrices and parity bits are separately calculated in two parts, as illustrated in FIG. 3. In this example, let a codeword length and a parity length be denoted by n and m, respectively. A message length is then (n−m). If a first parity length is g, a second parity length is (m−g).
FIG. 4 is a block diagram of an encoder configured to perform the conventional LDPC encoding method. Referring to FIG. 4, a pre-processor 45 decomposes a parity-check matrix into partition matrices as illustrated in FIG. 3. A first parity calculator 42 calculates first parity bits using the partition matrices and a second parity calculator 43 calculates second parity bits using the first parity bits. Input buffer 41 and output buffer 46 are also shown,
This method also further requires a memory 44 for storing the partition matrices in addition to an existing memory for encoding. For a codeword length of n, the pre-processing computation volume reaches 0(n3/2). Hence, as the codeword length is increased, the complexity also increases. A complexity of 0(n+g2) is required to calculate the first parity bits, and a complexity of 9(n) to calculate the second parity bits. Moreover, the inverse matrix of a certain matrix must exist to achieve the partition matrices.